import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 强仔
 * Date: 2022-04-27
 * Time: 21:10
 */
public class Main {
    public int findMaxGap(int[] A, int n) {
        int max = Integer.MIN_VALUE;
        int maxLeft = A[0];

        int maxRight = 0;
        for (int i = 0; i < n - 1; i++) {
            maxLeft = Math.max(maxLeft, A[i]);
            maxRight = A[i + 1];
            for (int j = i + 1; j < n; j++) {
                maxRight = Math.max(maxRight, A[j]);
            }
            max = Math.max(max, Math.abs(maxLeft - maxRight));
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] mat = {{4,46,89},{28,66,99},{26,21,71}};
        int[] result = clockwisePrint(mat, mat.length, mat[0].length);
    }
    public static int[] clockwisePrint(int[][] mat, int n, int m) {
        int[][] nextP = {{0,1},{1,0},{0,-1},{-1,0}};

        List<Integer> list = new ArrayList<>();

        boolean[][] book = new boolean[n][m];

        DFS(mat, n, m, list, 0, 0, nextP, book);

        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;

    }

    public static void DFS(int[][] mat, int n, int m, List<Integer> list, int newN, int newM, int[][] nextP, boolean[][] book){

        list.add(mat[newN][newM]);
        book[newN][newM] = true;

        for (int[] next : nextP) {
            int x = newN + next[0];
            int y = newM + next[1];
            if(x < n && x >= 0 && y < m && y >= 0 && !book[x][y]) {
                DFS(mat, n, m, list, x, y, nextP, book);
            }
        }
    }
}
